class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        qsort(stock,cnt,0,stock.size()-1);
        return{stock.begin(),stock.begin()+cnt};
    }

    void qsort(vector<int>& nums,int k,int l,int r)
    {
        if(l==r) return;

        int key=getRandom(nums,l,r);
        int left=l-1;
        int right=r+1;
        int i=l;
        while(i<right)
        {
            if(nums[i]<key){
                swap(nums[++left],nums[i++]);
            } 
            else if(nums[i]==key)
            {
                i++;
            }
            else {
                swap(nums[--right],nums[i]);
            }
        }
        int a=left-l+1,b=right-left-1;
        if(a>k)
        {
            return qsort(nums,k,l,left);
        }
        else if(a+b>=k) return;
        else return qsort(nums,k-a-b,right,r);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        int ra = rand();
        int key = nums[ra % (r - l + 1) + l];
        return key;
    }

};